class AVLNode {
  constructor(key, value){
    this.key = key;
    this.value = value;
    this.left = null;
    this.right = null;
    this.height = 1;
  }
}

class AVLTree {
  constructor() {
    this.root = null;
  }

  insert(key, value) {
    this.root = this._insert(this.root, key, value)
  }

  _insert(node, key, value) {

    /**
          20        height 3
        18   22     height 2
                23  新增节点 height 1；22 的 right 是 null；返回新 AVLNode
     */

    if (!node) return new AVLNode(key, value);
    
    if (key < node.key) {
      node.left = this._insert(node.left, key, value)
    }

    if (key > node.key) {
      node.right = this._insert(node.right, key, value)
    }

    if (key == node.key) {
      node.value = value
      return node
    }

    // 递归的更新每个父节点高度
    this.updateHeight(node);

    // 平衡
    this._balance(node)
  }

  updateHeight(node) {
    if (!node) return 0;
    // 左右都没有返回0，0 + 1 = 1 符合默认高度1
    node.height = Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1
  }

  getHeight(node) {
    return node ? node.height : 0
  }

  _balance(node) {
    const balanceFactor = this.getBalanceFactor(node);

    // LL情况（左子树高，且左子树的左子树最高）
    /**
            20
          18   22
        17
     16               新增节点 16，在第 18 触发右旋，左减右 得1
    */
    if (balanceFactor > 1 && this.getBalanceFactor(node.left) >= 0) { // 18的左是2，右是0，平衡因子 2
      return this.rightRotate(node)
    }

    // RR情况（右子树太高，且右子树的右子树最高）
    // -2 < -1
    /**
            20        height 3
          18   22     height 2
                  23  左减右 得-1
                    24  新增节点，在 22 触发左旋
    */
    if (balanceFactor < -1 && this.getBalanceFactor(node.right) <= 0) { // 22的左是0，右是2，平衡因子 -2
      return this.leftRotate(node)
    }

    // LR情况（根节点左子树最高，但左子树的右子树最高）
    /**
              21
            20   22
         17          23
           18         
             19       新增节点，在17触发RR左旋

              21
            20   22    17左旋后，在20触发LL右旋
          18      23
        17  19
    */
    if (balanceFactor > 1 && this.getBalanceFactor(node.left) < 0) { // 17的左是0，右是2，平衡因子是 -2
      node.left = this.leftRotate(node.left);
      return this.rightRotate(node);
    }

    // RL情况（根节点右子树最高，但是右子树的左子树最高）
    /**
               21
            20    25
                24    
              23       新增节点，在25触发LL右旋
                     
            以 25 右旋后
            
               21
            20   24
               23   25
    */
    /**
                21
            20     27
                     28
                  24    
                23       新增节点，在27触发LL右旋，以 28 为基础进行右旋
                     
            以 28 右旋后

               21
            20   27
                    24
                 23     26
    */
    if (balanceFactor < -1 && this.getBalanceFactor(node.right) > 0) {
      node.right = this.rightRotate(node.right)
      return this.leftRotate(node)
    }
    return node
  }

  // 右旋
  rightRotate(node) {
    // 28 的左节点 24
    const left = node.left;
    // T2 为 28 的左节点的右节点 null
    const T2 = left.right;

    // 右旋，把 24 的右节点，设置为28
    left.right = node;
    // 把 24 设置为 24 的右节点（null）
    /**
                21
            20     27
                     28
                   24    
                23    28    之前 24 的右节点是null，使用 T2 变量进行记录了
                     

             21
          20    27
                 \
                 null      把 24 等于 T2
              23      28

          因为最后 return left，所以 27 的右节点连接 24
      
     */
    node.left = T2;

    this.updateHeight(node);
    this.updateHeight(left);

    return left;
  }

  // 左旋
  leftRotate(node) {
    const right = node.right;
    const T2 = right.left;

    // 旋转
    right.left = node;
    node.right = T2;

    this.updateHeight(node)
    this.updateHeight(right)

    return right
  }

  getBalanceFactor(node) {
    if (!node) return 0;
    return this.getHeight(node.left) - this.getHeight(node.right);
  }

  search(key) {
    return this._search(this.root, key)
  }

  _search(node, key) {
    if (!node) return null;
    if (key === node.key) return node.value;
    if (key < node.key) return this._search(node.left, key);
    return this._search(node.right, key)
  }

  delete (key) {
    this.root = this._delete(this.root, key)
  }

  _delete(node, key) {

    /**
           20
          /
        14
          \
           17       被删除节点；被替换为16
          /  \
         15  18     18 被 _balance 返回自身不变
            /  \
          16    19  16被删除
     */

    if (!node) return null;  

    if (key < node.key) {  // 5. 16 < 18；node是18，key是16
      node.left = this._delete(node.left, key)  // 6. node是18，left是16，key也是16。这里要操作 18 的 left；第七步返回null，18的 left 就是 null 了
    } else if (key > node.key) {
      node.right = this._delete(node.right, key)
    } else {

        // 情况1：没有子节点或只有一个子节点
        if (!node.left || !node.right) {  // 7. 从第6步 新递归进入这里，16的左右都是null，返回null，18的 left 就是 null 了
          const temp = node.left || node.right;
          node = temp || null
        } else {  // 1. 17左右都有节点，走到else，node.key == key
          // 情况2：有两个子节点，找到中序遍历后继节点
          const temp = this._minValueNode(node.right); // 2. 获取17的右侧最左节点 16
          node.key = temp.key; // 3. 将 17 替换为 16
          node.value = temp.value;
          node.right = this._delete(node.right, temp.key) // 4. node.right是18，temp.key是16
        }

    }

    if (!node) return null; // 如果树为空，直接返回

    this.updateHeight(node);
    return this._balance(node);
  }

  _minValueNode(node) {
    let current = node;
    while (current && current.left) {
      current = current.left;
    }
    return current;
  }

  _preOrder(node, result = []) {
    if (node) {
      result.push({ key: node.key, value: node.value, height: node.height })
      this._preOrder(node.left, result)
      this._preOrder(node.right, result)
    }
    return result
  }

  // 前序遍历
  preOrder() {
    return this._preOrder(this.root)
  }

  // 中序遍历
  inOrder() {
    return this._inOrder(this.root)
  }

  _inOrder(node, result = []) {
    if (node) {
      this._inOrder(node.left, result);
      result.push({ key: node.key, value: node.value });
      this._inOrder(node.right, result);
    }
    return result;
  }

  getTreeHeight() {
    return this.getHeight(this.root)
  }

  // 判断树是否为空
  isEmpty() {
      return this.root === null;
  }
}

